package leetcode.code0560;

/**
 * 超内存限制
 *
 * @author CaoYu
 * @date 2021年11月5日
 * @description
 */
public class Solution extends Solution560 {

	private static final int OFF = 2 * (int) 10e4 * 1000;

	private static final int SIZE = OFF * 2 + 1;

	@Override
	public int subarraySum(int[] nums, int k) {
		int ans = 0;// 答案
		int[] hash = new int[SIZE];// hash[m]=n 累加和为m的有n个
		hash[OFF] = 1;// 累加和是0有1个
		int sum = 0;// 累加和
		for (int num : nums) {
			sum += num; // 当前累加和
			ans += hash[sum - k + OFF]; // 之前累加和为sum-k的有多少个都是答案
			hash[sum + OFF]++;// 更新累加和为sum的子数组数量
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();

	}

}
